package com.niuke;

import com.leetCode.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-16 14:58:44
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-16     张李鑫                     1.0         1.0 Version
 */
public class JZ32 {

    /**
     * 不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。
     * @param root
     * @return
     */
    public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        if (root==null){
            return new ArrayList<>();
        }
        Queue<TreeNode> stack = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.poll();
            list.add(pop.val);

            if (pop.left!=null){
                stack.add(pop.left);
            }
            if (pop.right!=null){
                stack.add(pop.right);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);


        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;

        System.out.println(PrintFromTopToBottom(treeNode1));
    }
}
